package com.mzy.linear_struct.hot100.二叉树;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: mizy3
 * @Date: 2024/08/21/下午10:36
 * @Description:
 */
public class Pro230二叉搜索树中第K小的元素 {
    int count;
    int res;
    public int kthSmallest(TreeNode root, int k) {
        count = k;
        inorder(root);
        return res;
    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        inorder(root.left);
        if(--count == 0) res = root.val;
        inorder(root.right);
    }



    /*    public int kthSmallest(TreeNode root, int k) {
        if(root == null) return -1;
        // 1 2 3 4
        List<Integer> ans = new ArrayList<>();
        inorder(root, ans);

        return ans.get(k - 1);
    }

    private void inorder(TreeNode root, List<Integer> ans) {
        if (root == null) {
            return;
        }

        inorder(root.left, ans);
        ans.add(root.val);
        inorder(root.right, ans);
    }*/

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(3, new TreeNode(1, null, new TreeNode(4)), new TreeNode(4));
        new Pro230二叉搜索树中第K小的元素().kthSmallest(treeNode, 1);
    }

}
